The quality of code produced by compilers has been an issue ever since the first compiler was produced. One of the principal objectives of IBM's FORTRAN I compiler, the first commercially available compiler, was to produce object code in the field of scientific computations which was comparable in code quality to that produced directly by assembly language programmers coding "by hand."
Today, higher level languages are designed to be used in every field in which computers are applicable. Even the original FORTRAN language has been bolstered to make it applicable to a wide range of programming tasks. However, it is still important that the quality of code produced by the compiler be high, especially if the resultant code is to be used in a production environment. Code produced by a skilled assembly language programmer is still the yardstick against which compiler produced code is measured.
A large number of optimization techniques have been developed and refined since the 1950's to improve the quality of compiler generated code. Indeed, many of these optimizations were known in principle, and used in some fashion by the team that produced the first FORTRAN compiler.
Optimizations that are frequently employed in optimizing compilers can be divided into two classes, which are commonly known as "global" and "peephole" optimizations. Global optimizations are those that are based on an analysis of the entire program being compiled. Examples are "code motion" (moving code out of loops) and "common subexpression elimination." Peephole optimizations are those that are based on an analysis of a relatively small region of the program, such as a "basic block," or perhaps only two adjacent instructions.
The present invention can be implemented as a global optimization or as a basic block optimization. It is described here as a global optimization, in which form it is most effective. The only information it needs from global analysis is that of live/dead information, in the form of a "last use" or "not last use" indication associated with each register operand of each instruction. This information tells, for each register operand of an instruction, whether or not that register can be used again before it is reloaded with a new quantity.
The following references discuss live variable analysis:
J. D. Ullman, "A Survey of Data Flow Analysis Techniques," Second USA-Japan Computer Conference Proceedings, AFIPS Press, Montvale, N.J., pp 335-342 (1975), (contains 37 references). PA0 A. V. Aho and J. D. Ullman, "Principles of Compiler Design," Addison-Wesley, (1977). PA0 M. S. Hecht, "Flow Analysis of Computer Programs," Elsevier North-Holland, New York, (1977).